package Z代码随想录.数组;

public class Leetcode209 {
    // 长度最小的子数组
    // 方法一，暴力解法，就是两层 for 循环 ，来列出所有可能的 符合的子序列，然后找到长度最小的直接返回
    // 外层控制 子序列的开始位置， 内层控制子序列的结束位置

    public static int minSubArrayLen1(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int subLength = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                // 发现子序列和超过 target值
                if (target <= sum) {
                    // 就记录此时自序列的长度
                    subLength = j - i + 1;
                    // 把结果更新到 ans 中 , 如果 ans 比 subLength 小，那么还是他自己，如果比subLength 大，就更新为 subLength
                    ans = ans < subLength ? ans : subLength;
                    // 更新后，就退出循环
                    break;
                }
            }
        }
        // 经过所有的循环后
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    // 滑动窗口的思想关键之处，在于 定义 j 结束位置！
    public static int minSubArrayLen(int target ,int[] nums){
        int i = 0; // 表示起始位置
        int sum = 0; // 初始和
        int ans = Integer.MAX_VALUE;
        int subLength = 0;
        for (int j = 0; j < nums.length; j++) {
            // 先累加和，此处的j为终点位置
            sum += nums[j];
            // 当累加和 大于等于 target的时候，进行更新
            while (sum >= target){
                subLength = j - i + 1;  // 当前子序列的长度
                // 与现有的 ans 进行比较，如果比ans小就更新
                ans = ans < subLength ? ans : subLength;
                // 然后开始滑动起始位置
                sum -= nums[i++];
            }
            // 此时不满足 sum >= target 的情况下, j就继续往后走
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2,3,1,2,4,3};
        int ret1 = minSubArrayLen(7,array);
        System.out.println(ret1);
        int ret2 = minSubArrayLen1(7,array);
        System.out.println(ret2);

    }
}
